The present invention generally relates to multicasting in a network, and more specifically, to a method and system for providing improved multicast key management in a network.
Using modern technologies that are available today, content delivery systems are capable of delivering contents over computer networks to a large number of users. A typical content delivery system includes a caching server responsible for delivering contents and a large number of clients or client applications that are under the control of the users. For example, a content delivery system may need to support hundreds of thousands, and possibly even millions, of users viewing a single event or program. In some cases, the programs are lengthy in duration and users are interested in only viewing some portion of a program (e.g., Olympics, shopping channel, news etc.). In order to charge users for such programming, it then becomes necessary to support a pay-by-time model. In a pay-by-time model, a user is charged only for the portion of the program that he or she consumed.
In a secure set-top client, such pay-by-time functionality may be more easily implemented in a secure manner. For example, tamper-proof hardware can be used in the set-top client to report in an accurate manner the amount of time that the client tuned in to a particular program. However, a general personal computer (PC) client cannot be trusted to perform such a task securely. This is because such PC client can be easily hacked. As a result, in order to support pay-by-time functionality with untrusted clients, a program needs to be delivered in a secure manner. One way to assure secure delivery of a program is to divide the program into program segments. There is a unique program segment key associated with each program segment, where the program segment key could be either used to encrypt the content within that program segment directly or it can be used to encrypt multiple content keys. A user that is authorized for a particular program segment will get the corresponding program segment key and will use it to decrypt the multiple content keys that are in turn used to decrypt the content within the program segment for viewing. In this manner, users that decide to leave a multicast or broadcast program would simply not be given more program segment keys for the following program segments, while the remaining users would continue receiving new program segment keys to allow them to continue viewing.
One straight-forward approach to support pay-by-time key management is to individually deliver the next program segment key to each user that remains in the multicast or broadcast group. This approach presents a number of problems. For example, for large multicast groups, this approach requires delivering program segment keys well ahead of time to ensure that such keys are delivered in time for each user. Even then, pay-by-time system scalability is severely limited by re-keying and the size of each program segment must be sufficiently large to insure that subsequent program segment keys can be delivered in time.
A number of multicast re-keying approaches have been proposed in an attempt to solve the foregoing problem. Many of these approaches are efficient at revoking a few users at a time from a multicast group and are based on the assumption that users leave at a constant rate. However, in practical situations, a large number of users may leave and users cannot be expected to leave a multicast group on a constant basis. To the contrary, user departure rate tends to fluctuate widely over the course of a program. For example, a large number of users tend to all want to leave a multicast group after some logical portion of the program is over (e.g., a specific Olympic event). Hence, these existing approaches still do not provide sufficient scalability that would efficiently accommodate varying user departure rate, such as, when a large number of users decide to leave a multicast group within a short period of time (e.g., within the same program segment).
In one of the proposed multicast key management schemes commonly known as the subset-difference method, each user is placed as a leaf into a binary tree and is given a subset of keys in that tree that depends on the user's position in that tree. The first time that a subgroup of users needs to be revoked from the group, the overhead of removing such subgroup of users from the group is proportional to the size of the to-be-revoked subgroup. This appears to provide as much scalability as can be expected. However, as time goes on and additional users leave the group, the overhead of removing such subsequent users becomes proportional to the number of users that have left the group since the beginning of the event. Consequently, as more and more users leave the group, the ability to revoke users from the group will likely degrade to an unacceptable level.
For purposes of illustration and simplicity herein, it should be understood that a user can be either a person or a client or client application or device that is under the control of a user.
FIG. 1 is a simplified schematic diagram illustrating a set of users belonging to a particular multicast group that have been arranged into a binary tree according to the subset-difference method. The binary tree has a number of nodes V1-V15 and a number of leaves V16-V31. The leaves of the tree V16-V31, represent the actual users and the leaves that are shaded, V18, V19, V21, V24, V25, V26 and V27, correspond to users that are to be revoked from the group.
The binary tree is further divided into subtrees that are rooted at nodes V4, V5 and V3. Each of these subtrees contains an inner subtree, where an inner subtree includes only the to-be-revoked leaves. For example, for a subtree rooted at node V4, there is an inner subtree rooted at node V9 that contains only the to-be-revoked leaves, V18 and V19.
The main idea of the subset-difference method is to have a key for each of the outer subtrees that is known to everyone in the outer subtree but not known to anyone inside the inner (revoked) subtree. This key is designated as LI,J. For example, for the outer subtree rooted at node V4, this outer subtree including node V8 and leaves V16 and V17, there is a key L4,9 that is known only to leaves V16, V17 but not to leaves V18, V19. In this example, in order to revoke leaves V18, V19, V21, V24, V25, V26 and V27, a new content key (CK) is sent out encrypted using the following difference keys: L4,9, L5,21 and L3,6.
Keys LI,J are generated as follows. First, each inner node VI in the tree is assigned a unique and independent label LABELI. Then, a “difference label” for the left child of VI is derived using an one-way function GL: GL (LABELI). Similarly, for the right child of VI, a difference label GR(LABELI) is created. Next, in order to compute a difference label LABELI,J for an outer subtree rooted at node VI and an inner subtree rooted at node VJ, one has to start with the original label LABELI for node VI and then derive the difference label by applying functions GL and GR multiple times, depending on the path between VI and VJ. For example, label LABEL3,28=GL(GL(GR(LABEL3))). The key LI,j is then computed by simply applying another one-way function GM to the difference label LABELI,J, i.e., LI,J=GM(LABELI,J).
When a particular leaf “u” is first initialized (i.e., when joining a multicast), this leaf “u” receives the following labels: for every VI ancestor of leaf “u”, leaf “u” receives all difference labels that are “hanging off the path” from VI to leaf “u”. From each of the labels, leaf “u” can derive the keys that it needs. For example, the path from root V1 to leaf V22 is as follows: V1, V2, V5, V11 and V22. When leaf V22 is initialized, it would receive the following difference labels:
LABEL1,3, LABEL1,4, LABEL1,10, LABEL1,23,LABEL2,4, LABEL2,10, LABEL2,23,LABEL5,10, LABEL5,23,LABEL11,23The foregoing is graphically illustrated in FIG. 2.
Referring back to FIG. 1, in order to revoke the indicated leaves (V18, V19, V21, V24, V25, V26 and V27), as previously mentioned, the new content key is sent out encrypted using L4,9, L5,21 and L3,6. In order for V22 to obtain the new content key, V22 derives L5,21 from LABEL5,10 (which it was given during initialization) as follows:L5,21=GM(LABEL5,21)=GM(GR(LABEL5,10))The number of keys received by a leaf “u” during initialization turns out to be:Log(N)+(Log(N)−1)+(Log(N)−2)+ . . . +1=Log(N)*(Log(N)+1)/2The foregoing can be simplified to O(log(N)2), where O(N) is the number of messages required for one rekeying for N users participating in the multicast. For example, with N=8 million ˜223, each user joining a multicast would get initialized with two hundred and seventy-six (276) keys. In the case that each key is one hundred and twenty-eight (128) bits (or sixteen (16) bytes) in length, this would require 276*16˜4.5 Kbytes of key storage. Where a security chip is utilized, these keys would probably have to be stored encrypted outside of the chip. Details of the subset-difference method can be further found in the publication, “Revocation and Tracing Schemes for Stateless Receivers”, by D. Naor et al., the disclosure of which is hereby incorporated by reference in its entirety for all purposes.
One main problem with the subset-difference method is that once some users in the group are revoked, none of the inner node labels and none of the difference keys are modified. As a result, in order to insure that the previously revoked users do not receive any more content keys, these users have to be counted as to-be-revoked users during each rekeying even though they have already been revoked previously. In other words, during each rekeying, previously revoked users have to be counted again for revocation purposes. Thus, the number of to-be-revoked leaves R grows each time and could eventually approach the total number of leaves N in the tree.
It would be impractical to modify the inner node labels during each rekeying because of the way the keys are derived from the labels. For example, if root label LABEL1 is modified, it automatically affects the values of all of the difference labels LABEL1,x and most of the leaves in the tree will have to be updated with some new difference labels. Consequently, modifying the inner node labels during each rekeying presents a scalability problem.
In addition to this problem, since each user of the group has to be initialized with a considerable amount of keying material which in the worst case scenario could amount to several Kbytes, it would be impractical to initialize each user joining a multicast with all of the necessary labels at the time s/he joins the multicast.
Hence, it would be desirable to provide an improved subset-difference method that is able to improve multicast key management in a network to allow for more efficient revocation of users from a group and conversely rekeying of remaining users.